#include<iostream>
#include<fstream>
#include<cstdlib>
#include<sstream>
#include<queue>
using namespace std;
const int N = 10000, M = N * N;
int h[N], e[M], w[M], ne[M], s[M];
long long idx;
void add(int a, int b, int c) {
	s[idx] = a, e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int main(int argc,char** args){
//生成保证连通的正权图，不保证没有自环，最短路算法源点应设置在1号点
	rand();rand();rand();rand();rand();rand();
	for (int n = 100,cnt=1; n <= 10000; n *= 2,++cnt) {
		queue<int>q;
		q.push(1);
		int cnt1 = 1, cnt2 = 0, depth = 0, num_vertex = 1;
		while (!q.empty()) {
			int t = q.front();
			q.pop();
			int num_sons = rand() % 10+1;
			cnt2 += cnt1--;
			if (!cnt1) {
				++depth;
				swap(cnt1, cnt2);
			}
			for (int i = 1; i <= num_sons; ++i) {
				add(t, t + i, rand() % n+n);
				q.push(t+i);
				for(int j=1;j<=num_vertex;++j)
					add(t+i,j,rand()%(n/depth)+1);
				++num_vertex;
			}
			if (num_vertex >= n-15)break;
		} 
		stringstream ss;
		ss << "input" << cnt << ".txt";
		ofstream ofs;
		ofs.open(ss.str());
		ofs << num_vertex << " " << idx << endl;
		for (int i = 0; i < idx; ++i) {
			ofs << s[i] << " " << e[i] << " " << w[i] << " " << endl;
		}
		printf("%d vertex %d edges  have been generated\n", num_vertex,idx);
	}

}